#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;


//递归超时，尝试用动态规划
// class Solution {
// public:
//     int numDecodings(string s) {
//         int result  = 0;
//         func(s,0,result);
//         return result;

//     }
//     void func(string& s, int index,int& result){
//         if(index>s.size()){
//             return;
//         }
//         if(index == s.size()){
//             result += 1;
//             return;
//         }
        
//         if(s[index]!='0'){
//             func(s,index+1,result);   
//         }
//         if(s[index]!='0'&&index+1<s.size()){
//             string temp = "";
//             temp = temp + s[index]+s[index+1];
//             if(temp<="26"){
//                 func(s,index+2,result);
//             }
//         }
//     }
// };


class Solution {
public:
    int numDecodings(string s) {
        //dp[i]表示以i结尾有多少个
        if(s[0]=='0'){
            return 0;
        }
        vector<int> dp(s.size(),0);
        dp[0] = 1;
        if(s.size()>=2){
            string temp = "";
            temp = temp+s[0]+s[1];
            if(stoi(temp)<=26&&s[1]!='0'){
                dp[1] = 2;
            }
            else if(s[1]=='0'&&stoi(temp)>26){
                dp[1] = 0;
            }
            else{
                dp[1] = 1;
            }
            
        }
        for(int i = 2;i<s.size();++i){
            if(s[i]!='0'){
                string temp = "";
                temp = temp+s[i-1]+s[i];
                if(s[i-1]!='0'&&stoi(temp)<=26){
                    dp[i] = dp[i-2]+dp[i-1];
                }
                else if(s[i-1]=='0'||stoi(temp)>26){
                    dp[i] = dp[i-1];
                }
                else{
                    return 0;
                }
            }
            else{
                if(s[i-1]!='0'&&s[i-1]<'3')
                    dp[i] = dp[i-2];
                else if(s[i-1]=='0'){
                    return 0;
                }
                
            }
        }
        
        return dp[s.size()-1];
    }
};


int main(){
    Solution S;
    cout<<S.numDecodings("301")<<endl;
}